package algorithm.array;

//给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 输入：nums = [3,0,1]
 *         输出：2
 *         解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 */

public class MissingNumber {

    public static void main(String[] args) {

        int [] nums = {1,2,3,4};
        System.out.println(missingNumber1(nums));
    }

    public static int missingNumber(int[] nums) {

        int value = 0;
        Map<Integer, Integer> map = new HashMap<>();

        int [] nums1 = new int[nums.length+1];
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = i;
        }

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                continue;
            }else{
                value = nums1[i];
            }
        }

        return value;
    }

    public static int missingNumber1(int[] nums) {
         Set<Integer> set = new HashSet<>();
         for(int i = 0; i < nums.length; i++) set.add(nums[i]);
         for(int i = 0; i <= nums.length; i++)
             if(!set.contains(i)) return i;
         return -1;
    }
}
